home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / wtek0693.zip / OOPALLEY.ZIP / ORDCLTN.CPP < prev    next >
C/C++ Source or Header  |  1993-04-27  |  8KB  |  308 lines
  1. #include <stdlib.h>     //  prototype for qsort
  2. #include "ordcltn.h"
  3.  
  4. #define THIS    OrderedCltn
  5. #define BASE    SeqCltn
  6. DEFINE_CLASS(OrderedCltn,SeqCltn);
  7.  
  8. OrderedCltn::OrderedCltn(unsigned size) : contents(size)
  9. {
  10.     endIndex = 0;
  11. }
  12.  
  13. OrderedCltn::OrderedCltn(const OrderedCltn& c) : contents(c.contents)
  14. {
  15.     endIndex = c.endIndex;
  16. }
  17.  
  18. void OrderedCltn::operator=(const OrderedCltn& c)
  19. {
  20.     endIndex = c.endIndex;
  21.     contents = c.contents;
  22. }
  23.  
  24. bool OrderedCltn::operator==(const OrderedCltn& a) const
  25. {
  26.     if (endIndex != a.endIndex) return NO;
  27.     else {
  28.         register int i = endIndex;
  29.         register Object** vv = &contents.elem(0);
  30.         register Object** av = &a.at(0);
  31.         while (i--) if (!((*vv++)->isEqual(**av++))) return NO;
  32.     }
  33.     return YES;
  34. }
  35.  
  36. OrderedCltn OrderedCltn::operator&(const SeqCltn& cltn) const
  37. {
  38.     OrderedCltn c(size()+cltn.size());
  39.     addContentsTo(c);
  40.     cltn.addContentsTo(c);
  41.     return c;
  42. }
  43.  
  44. void OrderedCltn::operator&=(const SeqCltn& cltn)
  45. {
  46.     cltn.addContentsTo(*this);
  47. }
  48.  
  49. Object* OrderedCltn::addAtIndex(int i, const Object& ob)
  50. {
  51.     if (endIndex == capacity()) contents.reSize(capacity()+CLTN_EXPANSION_INCREMENT);
  52.     for (register int j=endIndex; j>i; j--) contents[j] = contents[j-1];
  53.     contents[i] = (Object*)&ob;
  54.     endIndex++;
  55.     return (Object*)&ob;
  56. }
  57.  
  58. Object* OrderedCltn::removeAtIndex(int i)
  59. {
  60.     register Object* obrem = contents[i];
  61.     for (register int j=i+1; j<endIndex; j++) contents[j-1] = contents[j];
  62. #if 0
  63.     if (endIndex < capacity()) contents[endIndex--] = (Object*)nil;
  64. #else
  65.     // -gmv 2/2/90
  66.     // Modified to handle deletion of item
  67.     // even when collection is full to capacity.
  68.     // endIndex should always be decremented.  But the item
  69.     // just beyond it is not set to nil if the collection was
  70.     // filled to capacity just prior to the deletion.
  71.  
  72.     if (endIndex < capacity()) contents[endIndex] = (Object*)nil;
  73.     --endIndex;
  74. #endif
  75.     return obrem;
  76. }
  77.  
  78. Object* OrderedCltn::add(const Object& ob)
  79. {
  80.     addAtIndex(endIndex,ob);
  81.     return (Object*)&ob;
  82. }
  83.  
  84. Object* OrderedCltn::addAfter(const Object& ob, const Object& newob)
  85. {
  86.     register int i = indexOf(ob);
  87.     if (i < 0) errNotFound("addAfter",ob);
  88.     return addAtIndex(i+1,newob);
  89. }
  90.  
  91. Object* OrderedCltn::addAllLast(const OrderedCltn& cltn)
  92. {
  93.     if (endIndex+cltn.size() >= capacity())
  94.         contents.reSize(endIndex+cltn.size()+CLTN_EXPANSION_INCREMENT);
  95.     for (register int i=0; i<cltn.size(); i++) contents[endIndex++] = cltn.contents[i];
  96.     return (Object*)&cltn;
  97. }
  98.  
  99. Object* OrderedCltn::addBefore(const Object& ob, const Object& newob)
  100. {
  101.     register int i = indexOf(ob);
  102.     if (i < 0) errNotFound("addBefore",ob);
  103.     return addAtIndex(i,newob);
  104. }
  105.  
  106. Collection& OrderedCltn::addContentsTo(Collection& cltn) const
  107. {
  108.     for (register int i=0; i<size(); i++) cltn.add(*contents[i]);
  109.     return cltn;
  110. }
  111.  
  112. Object* OrderedCltn::addLast(const Object& ob) { return add(ob); }
  113.  
  114. Object* OrderedCltn::after(const Object& ob) const
  115. {
  116.     register int i=indexOf(ob);
  117.     if (i<0) errNotFound("after",ob);
  118.     if (++i == endIndex) return (Object*)nil;
  119.     return contents[i];
  120. }
  121.  
  122. Object*& OrderedCltn::at(int i) const { return (*this)[i]; }
  123.  
  124. void OrderedCltn::atAllPut(const Object& ob)
  125. {
  126.     for (register int i=0; i<endIndex; i++) contents[i] = (Object*)&ob;
  127. }
  128.  
  129. Object* OrderedCltn::before(const Object& ob) const
  130. {
  131.     register int i = indexOf(ob);
  132.     if (i < 0) errNotFound("before",ob);
  133.     if (--i < 0) return (Object*)nil;
  134.     return contents[i];
  135. }
  136.  
  137. unsigned OrderedCltn::capacity() const   { return contents.capacity(); }
  138.  
  139. void OrderedCltn::deepenShallowCopy()
  140. {
  141.     BASE::deepenShallowCopy();
  142.     contents.deepenShallowCopy();
  143. }
  144.  
  145. #pragma warn -rvl   // Turn of Warning: Function should return a value
  146. Object* OrderedCltn::first() const
  147. {
  148.     if (endIndex==0) 
  149.     {
  150.         errEmpty("first");                          // aborts, return not executed
  151.         // return (Object*)NULL;                       // avoids Warning message
  152.     } else 
  153.         return contents.elem(0);
  154. }
  155. #pragma warn .rvl
  156.  
  157. unsigned OrderedCltn::hash() const
  158. {
  159.     register unsigned h = endIndex;
  160.     register int i = endIndex;
  161.     register Object** vv = &contents.elem(0);
  162.     while (i--) h^=(*vv++)->hash();
  163.     return h;
  164. }
  165.  
  166. int OrderedCltn::indexOf(const Object& ob) const
  167. {
  168.     for (register int i=0; i<endIndex; i++)
  169.         if (contents[i]->isEqual(ob)) return i;
  170.     return -1;
  171. }
  172.  
  173. int OrderedCltn::indexOfSubCollection(const SeqCltn& cltn, int start) const
  174. {
  175.     int subsize = cltn.size();
  176.     for (register int i=start; i<(endIndex-subsize); i++) {
  177.         for (register int j=0; j<subsize; j++)
  178.             if (!(contents[i+j]->isEqual(*cltn.at(j)))) goto next;
  179.         return i;
  180. next:;  }
  181.     return -1;
  182. }
  183.  
  184. bool OrderedCltn::isEmpty() const { return endIndex==0; }
  185.     
  186. bool OrderedCltn::isEqual(const Object& a) const
  187. {
  188.     return a.isSpecies(class_OrderedCltn) && *this==*(OrderedCltn*)&a;
  189. }
  190.  
  191. const Class* OrderedCltn::species() const
  192. {
  193.     return &class_OrderedCltn;
  194. }
  195.  
  196. #pragma warn -rvl   // Turn of Warning: Function should return a value
  197. Object* OrderedCltn::last() const
  198. {
  199.     if (endIndex==0) 
  200.     {
  201.         errEmpty("last");                           // aborts, return not executed
  202.         //return (Object*)NULL;                       // avoids Warning message
  203.     } else 
  204.         return contents.elem(endIndex-1);
  205. }
  206. #pragma warn .rvl
  207.  
  208. unsigned OrderedCltn::occurrencesOf(const Object& ob) const
  209. {
  210.     register unsigned n=0;
  211.     for (register int i=0; i<endIndex; i++)
  212.         if (contents[i]->isEqual(ob)) n++;
  213.     return n;
  214. }
  215.  
  216. void OrderedCltn::printOn(ostream& strm) const
  217. {
  218.     strm << className() << "[\n";
  219.     for (register int i=0; i<endIndex; i++) {
  220.         if (i>0) strm << "\n";
  221.         contents[i]->printOn(strm);
  222.     }
  223.     strm << "]\n";
  224. }
  225.  
  226. Object* OrderedCltn::remove(const Object& ob)
  227. {
  228.     for (register int i=0; i<endIndex; i++) {
  229.         if (contents[i]->isEqual(ob)) {
  230.             return removeAtIndex(i);
  231.         }
  232.     }
  233.     return (Object*)nil;
  234. }
  235.  
  236. Object* OrderedCltn::removeId(const Object& ob)
  237. {
  238.     for (register int i=0; i<endIndex; i++) {
  239.         if (contents[i] == &ob) {
  240.             removeAtIndex(i);
  241.             return (Object*)&ob;
  242.         }
  243.     }
  244.     return (Object*)nil;
  245. }
  246.  
  247. #pragma warn -rvl   // Turn of Warning: Function should return a value
  248. Object* OrderedCltn::removeLast()
  249. {
  250.     if (endIndex==0) 
  251.     {
  252.         errEmpty("removeLast");                     // aborts, return not executed
  253.         // return (Object*)NULL;                       // avoids Warning message
  254.     } else 
  255.         return removeAtIndex(endIndex-1);
  256. }
  257. #pragma warn .rvl
  258.  
  259. void OrderedCltn::reSize(unsigned newSize)
  260. {
  261.     if (newSize > size()) contents.reSize(newSize);
  262. }
  263.  
  264. void OrderedCltn::replaceFrom(int start, int stop, const SeqCltn& replacement, int startAt)
  265. {
  266.     register int j=startAt;
  267.     for (register int i=start; i<=stop; i++,j++)
  268.         contents[i] = replacement.at(j);
  269. }
  270.  
  271. static int compare_ob(Object** a, Object** b) { return (*a)->compare(**b); }
  272.  
  273. unsigned OrderedCltn::size() const       { return endIndex; }
  274.  
  275. void OrderedCltn::sort()
  276. {
  277.      //qsort(&contents.elem(0),size(),sizeof(Object*),compare_ob);
  278.      qsort(&contents.elem(0),size(),sizeof(Object*),
  279.      (int (*)(const void*, const void*))compare_ob); //-gmv added cast
  280. }
  281.  
  282. void OrderedCltn::errEmpty(const char* fn) const
  283. {
  284.     DTerror("", "");
  285.     cerr << "Collection empty: "
  286.          << this << "->"
  287.          << className() << "::" << fn << "()"
  288.          << "\n";
  289. }
  290.  
  291. void OrderedCltn::errNotFound(const char* fn, const Object& ob) const
  292. {
  293.     DTerror("Object not found: ",className());
  294.     cerr << "Object not found: "
  295.          << this << "->"
  296.          << className() << "::" << fn
  297.          << "((" << ob.className() << "*)"
  298.          << &ob << ")"
  299.          << "\n";
  300. }
  301.  
  302. OrderedCltn Collection::asOrderedCltn() const
  303. {
  304.     OrderedCltn cltn(MAX(size(),CLTN_DEFAULT_CAPACITY));
  305.     addContentsTo(cltn);
  306.     return cltn;
  307. }
  308.